Кандидатов на присуждение звания "Почетный гражданин Москвы"могут выдвигать органы власти, организации и отдельные граждане. Претенденты рассматриваются специальной комиссией Мосгордумы и с ее разрешения выносятся на утверждение парламента.
10 июня 1996 года комиссия отказала в получении звания сразу 17 кандидатам, наиболее известным из которых был балетмейстер Игорь Моисеев.
1 июня 2000 года комиссия отбраковала восемь претендентов, среди которых были певицы Ирина Архипова и Людмила Зыкина, а также композитор Тихон Хренников. Тогда же комиссия одобрила кандидатуру художника Александра Шилова, которого выдвинул мэр Юрий Лужков с формулировкой "за заслуги перед столицей в развитии отечественной культуры и возрождение традиций меценатства". Это решение породило массу протестов. Так, директор Государственного института искусствознания Алексей Комич в письме в Мосгордуму заявил: "Уравнивать гражданский подвиг Павла Третьякова с подношением Шилова — это значит профанировать и звание "Почетный гражданин города Москвы", и бескорыстное дело меценатства". Мосгордума прислушалась, и господину Шилову звания не дала. 24 октября 2001 года ему было отказано повторно.
В ноябре 2002 года депутат Мосгордумы Татьяна Портнова предложила присвоить звание детскому хирургу Леониду Рошалю "за заслуги перед москвичами и содействие по спасению жизней заложников в театральном центре на Дубровке". Комиссия кандидатуру отклонила.
В ноябре 2004 года комиссия забраковала кандидатуры сразу двух Героев Советского Союза: военачальника, бывшего члена ЦК КПСС, председателя Российского комитета ветеранов войны и военной службы генерала армии Владимира Говорова и летчика, маршала авиации Анатолия Константинова, уточнив, что масштаб их личности достоин более широкого признания, чем муниципальная награда. В апреле 2005 года комиссия вновь отклонила кандидатуру господина Константинова и заодно — нобелевского лауреата Виталия Гинзбурга.