A remarkable interest in the Internet of Things (IoT)-based smart cities from both academia and industry has been observed in recent years. Smart cities can offer various smart applications such as intelligent transportation, industry 4.0, smart banking, among others, for boosting the life quality of citizens. Security is one of the key challenges of a smart city. One can enable smart cities with a blockchain to offer enhanced security via storing transactions in a secure, transparent, decentralized, and immutable ledger. However, both blockchain and smart cities are in their infancy and significant research efforts are needed to integrate them. In this paper, we comprehensively review the role of blockchain in enabling IoT-based smart cities. First, we present the evolution of blockchain technology in terms of constituent technologies, consensus algorithms, and blockchain platforms. Second, we discuss and critically evaluate various smart applications enabled by blockchain. Third, we present real-world blockchain implementation in smart cities as case studies. Fourth, we present the key requirements to integrate blockchain with smart cities. Finally, we present open research challenges along with their key causes and possible solutions.