Nastanek cerkve sega v 14. stoletje, njena predhodnica pa je na istem mestu stala že v romanskem času. Cerkev sv. Martina je bila v virih prvič omenjena leta 1342 kot vikariat prafarne župnije sv. Jurija v Hočah. Samostojna župnija je postala leta 1597.

Cerkvena stavba je bila v preteklosti večkrat predelana. Najzanimivejši del starega prezbiterija predstavljajo fantastične parlerjanske maske (ok. 1390), izklesane v konzolah in kapitelih služnikov, ter stenske slike s figuralnimi prizori iz 16. stoletja.

Sedanja novogotska stavba župnijske cerkve sv. Martina na Zgornji Hajdini je bila zgrajena po načrtih stavbenika V. Morandinija v letih 1873 in 1874.

Oltarji so izdelani v novogotskem slogu; od gotske opreme je ohranjen kamniti tabernakelj. Cerkev in njena notranja oprema sta bili v celoti obnovljeni v prvem desetletju 21. stoletja.

Župnijska cerkev sv. Martina je z Martinovo stopinjo (oznaka poti) vključena v evropsko kulturno pot sv. Martina Tourskega, ki je svojo življenjsko pot začel v Szombathelyu na Madžarskem in končal v Toursu v Franciji.

Hajdinska cerkev s starim patrocinijem sv. Martina je bila v 14. stoletju vikariatna cerkev v okviru hoške pražupnije. Leta 1398 si je odvetniške pravice nad cerkvijo pridobil Bernard Ptujski in jo dal v prvem desetletju 15. stoletja prezidati. Za dela je zaposlil mojstre kamnoseke, ki so delali na gradbišču romarske cerkve na Ptujski gori. Od Bernardovih prezidav je ohranjen prezbiterij, ki so ga v 19. stoletju kot stransko kapelo vključili v novo stavbo. Pozidan je v obliki kratkega kora z eno obočno polo in petosminskim sklepom ter pokrit z zvezdastim obokom. Rebra oboka so oprta na konzolo in šest kapitelov, ki so izklesani v obliki fantastičnih glav s človeškimi in živalskimi značilnostmi. Tovrstne podobe so bile v srednjeevropski arhitekturni plastiki 14. in zgodnjega 15. stoletja pogoste, vendar tako plastično modelirane in z obilo kiparske domišljije zasnovane, kot so na Hajdini, zasledimo le redko.