SHMKM "Nikolla Shtejn" – Tetovë është formuar në vitin 1961 me vendim nr:05-5685 nga ana e Kuvendit të komunës së Tetovës me emrin Shkolla e Mesme Medicinale për motra medicinale-teknik, ndësa në vitin 1979 me vendimin e Gjyqin e Qarkut në Shkup shkolla do të emërtohet Qendra shkollore medicinale "Nikolla Shtejn" si organizatë punëtore pa organizata bazë për punësimtë bashkuar.

Në vitin 1961 shkolla fillon të punoj vetëm me dy praralele në gjuhën maqedone derisa në vitin 1967/68 u hapën edhe paralele në gjuhën shqipe kurse më 1987/88 edhe në ghuhën turke.

Numri i nxënësve dhe paraleleve nga viti në vit rritet ashtu që  sot shkolla punon me 80 paralele në tri gjuhët mësimore të regjistruar në në 7 profile (motër medicinale, teknik dhëmbesh, teknik fizioterapeutik, teknik laborant medicinal, teknik farmaceutik, teknik) si dhe 2 profile nga lëmia e shërbimeve personale teknik optik dhe teknik kozmetik) nga profesionet e shëndetsisë me rreth 3000  nxënës.

Nga viti 2005/06 mësimi zhvillohet në një ndërtesë moderne të re me të gjitha kushtet për mësim të suksesëshëm sipas (Arsimim i mesëm i reformuar profesional)

Adresa e shkollës: Rr. Ilinden” pn.
Tel: 044 339 110
Faks: 044 332 511
E-mail: s.medicina@mt.net.mk