Lokalnie muchołówkę małą spotkać można na obrzeżach osiedli w Szczecinie, Warszawie, Białymstoku i Trójmieście, jak też w parkach Poznania i Kórnika w Wielkopolsce. Spośród parków narodowych najliczniej występuje w Białowieskim, Drawskim, Bieszczadzkim i Magurskim (w tym ostatnim 140–200 par). W Puszczy Białowieskiej żyje około 1300–1400 par. Rozmieszczenie, jak i liczebność muchołówki małej w Polsce w XIX w. i II połowie XX wieku było podobne. Wycinanie starodrzewi na wschodzie kraju na przełomie XIX w. i XX w. spowodowało spadek liczebności populacji. Obecnie populacje lokalnie rosną, np. w okolicach Warszawy ze względu na objęcie ochroną starych drzew. Wśród rodzimych gatunków muchołówek ta jest najmniejsza (jak wskazuje nazwa).
Według danych BirdLife International z 2015 roku europejska populacja liczy 3 290 000 – 5 090 000 par lęgowych. Według starszych danych (2000) najliczniej gatunek ten lęgnie się w Rosji (od 1 000 000 do 10 000 000 par), Białorusi (60 000 – 100 000 par), Łotwie (50 000 – 80 000), Słowacji (50 000 – 100 000), Rumunii (20 000 – 40 000) i na Litwie (15 000 – 25 000).