Tanī pat vietā, kur tagad atrodas Madlienas mūra baznīca, senāk bijusi maza koka baznīciņa. Apkārt šai mazajai baznīciņai bijušas mācītāja ēkas un aiz tām atkal parastās zemnieku būdiņas. Nedz baznīcai, nedz arī šai nelielajai mājiņu kopībai - ciematam - nebija sava nosaukuma. Nosaukums radies šādi.

Vecā koka baznīciņa bijusi jau pavisam veca. Ticis nolemts, ka jāmūrē jauna akmeņa baznīca. Mūra darbi tikuši uzsākti, bet bez kaut kādiem panākumiem: cik pa dienu uzmūrējuši, tik naktī sabrucis. Kāds burvju pēctecis, vecs galdnieks, sacījis, ka tikai tad baznīcu uzmūrēšot, ja tur iemūrēšot vienu jaunavu. Tomēr neviena madlēniete neuzdrošinājusies ļaut sevi iemūrēties. Tad mācītājs izdomājis kādu viltību. Viņš sarīkojis ļoti lielas dzīres. Pirmajā dzīru naktī, tā ap pusnakti, viņš ieaicinājis pie sevis divpadsmit no vīna apskurbušās jaunavas un jautājis, kura no viņām gribot valdīt jaunceļamās baznīcas atslēgas. Ciemata skaistākā jaunava Madaļa teikusi, ka viņa to vēloties darīt. Citas jaunavas tikušas izsūtītas ārā, izņemot Madaļu. Mācītājs devis viņai dzert no kāda kausa vīnu, no kura Madaļa iemigusi dziļā un cietā miegā. Izmantodami viņas miegu, mūrnieki to pa tumsu aiznesuši uz jaunceļamo baznīcu un tur iemūrējuši. Iemūrētā jaunava baznīcas sienā vēl mocījusies trīs dienas, līdz pēdīgi tad arī nomirusi. Stāsta, ka ļaudis visas šīs trīs dienas, kamēr Madaļa pa baznīcas mūri mocījusies, naktī pat acis aizvērt nevarējuši, jo bijusi sadzirdama mocekles rūkšana baznīcas mūrī. Kad Madaļa pēdīgi nomirusi, mūris ticis mūrēts tālāk bez kaut kādiem traucējumiem. Madaļai par godu tad arī baznīca un pie tās atrodošais ciemats ticis nosaukts viņas vārdā par Madlienu.