We prove convergence and optimal complexity of an adaptive finite element algorithm on quadrilateral meshes. The local mesh refinement algorithm is based on regular subdivision of marked cells, leading to meshes with hanging nodes. In order to avoid multiple layers of these, a simple rule is defined, which leads to additional refinement. We prove an estimate for the complexity of this refinement technique. As in former work, we use an adaptive marking strategy which only leads to refinement according to an oscillation term, if it is dominant. In comparison to the case of triangular meshes, the a posteriori error estimator contains an additional term which implicitly measure the deviation of a given quadrilateral from a parallelogram. The well-known lower bound of the estimator for the case of conforming P 1 elements does not hold here. We instead prove decrease of the estimator, in order to establish convergence and complexity estimates.