V devadesátých letech řešily ŽSR stejně jako ČD problém s nehospodárností a klesající spolehlivostí lokomotiv řady 735. Ještě před rozdělením drah byla sice lokomotiva řady 735 rekonstruována na stroj 714.001, ta ale připadla ČD a další, tentokrát sériové rekonstrukce byly prováděny pouze pro ČD. Ke stavu strojů řady 735 se navíc přidružila i potřeba lehčí lokomotivy, umožňující všestranné využití. Proto byly zahájeny projekční práce (v režii ŽOS Zvolen a ČMKS) na komplexní rekonstrukci lokomotiv 735. V roce 1998 byl konečně vyroben prototyp 736.016, což byla rekonstruovaná lokomotiva 735.016. Přestavbu provedly Železničné opravne a strojárne Zvolen, konstrukce lokomotivy je ale "slovensko-česká". Lokomotiva byla záhy přeznačena na 736.001. Na mezinárodní výstavě ŽEL-RAIL byla lokomotiva oceněna zlatou medailí. Lokomotiva 736.002 byla dokončena v roce 2002 a další lokomotivy následovaly od roku 2003. Dnes (březen 2005) je rekonstruováno 12 lokomotiv, smlouva je na 18 strojů. Původně měla být výroba ukončena v letošním roce, nakonec budou letos vyrobeny 3 lokomotivy a zbylé 3 lokomotivy budou následovat v roce 2006.
Zkoušky prototypu probíhaly zejména na ŽZO Cerhenice. V rámci zkoušek byla lokomotiva nasazována na poštovní a osobní vlaky. Dnes lokomotivy slouží ve vozbě osobních vlaků, lehčích nákladních vlaků a vhodné jsou i pro těžší posun, kde se uplatňuje jejich vysoká tažná síla. Stroje 736.007 až 010 byly po vyrobení dodány do depa Nové Zámky, byly ale redislokovány a dnes jsou všechny stroje dislokovány v RD Zvolen. Dá se říct, že lokomotivy 736 ZSSK jsou obdobou řady 714 ČD, neboť jejich základ, parametry i provozní určení si jsou navzájem velmi podobné. Rekonstrukce na řadu 736 jsou ale řešeny nesporně velkoryseji než na řadu 714 (i když tyto rekonstrukce jsou staršího data).
Jedná se o vysoce sofistikovanou a ekologickou lokomotivu. Lokomotiva je dvoupodvozková kapotová, s nestejně dlouhými kapotami a věžovou kabinou strojvedoucího. Kabina strojvedoucího se dvěma diagonálními řídicími pulty je vybavena bezpečnostními skly, klimatizací, je tepelně a hlukově izolována a ve výbavě nechybí umyvadlo, mikrovlnná trouba, chladnička a šatník. Hlavní rám i s podvozky byl převzat z lokomotiv řady 735, došlo ale k některým úpravám (rekonstrukce schůdků, nové odpružení tahadel, umístění deformačních členů za nárazníky). V hlavním rámu lokomotivy jsou zalisovány otočné čepy, které rám spojují se dvěma dvounápravovými hnacími podvozky. Dvojkolí jsou v nich vedena kyvnými rameny, odpruženými vinutými ocelovými pružinami, doplněnými ve svislém směru kapalinovými tlumiči. Podvozky byly doplněny zařízením RailJet pro mazání okolků. V každém podvozku jsou umístěny dva trakční elektromotory s tlapovými ložisky. Rám je na podvozcích uložen prostřednictvím pryžokovových silentbloků. Část lokomotivy nad hlavním rámem je zcela nově řešena. V přední, delší kapotě se nachází hlavní motorgenerátorové soustrojí, pomocný motorgenerátor, chladicí soustava a pneumatická výzbroj. Hlavní motorgenerátor se používá při traťové službě a těžším posunu, pomocný motorgenerátor má využití při jízdě samotné lokomotivy nebo při lehkém posunu a stání. Hlavní trakční soustrojí se složeno ze spalovacího motoru Caterpillar 3512 DI-TA a alternátoru, spřaženého s dieselem spojkou Centamax. Spalovací motor je čtyřdobý vznětový dvanáctiválec s válci do V, přímým vstřikem paliva, přeplňováním a kapalinovým chlazením. Pružnou spojkou je k tomuto motoru připojen topný alternátor, rovněž od firmy Siemens. Hlavní trakční soustrojí je umístěno přibližně v polovině delšího představku. Veškeré rizikové okruhy jsou chráněny proti úniku ropných látek. V zadní části představku přiléhá ke stěně kabiny strojvedoucího pomocné trakční soustrojí, sestávající ze čtyřdobého vznětového řadového přímovstřikového šestiválce s přeplňováním a vodním chlazením Caterpillar 3056 DI-TA, a alternátoru. Brzdový systém lokomotivy je tvořen ruční brzdou, samočinnou tlakovou brzdou systému DAKO GP, přímočinnou brzdou, parkovací brzdou a elektrodynamickou brzdou. Samočinná i přímočinná brzda mají elektrické brzdiče. Lokomotiva má dva hlavní vzduchojemy o objemu celkem 1 000 l, napájené stlačeným vzduchem od elektricky poháněného šroubového kompresoru Atmos LE 180. Písty brzdových válců (dva v každém podvozku) o průměru 8" jsou spřaženy se špalíky třecí brzdy, brzdící oboustranně všechna dvojkolí. Ve službě lokomotiva disponuje zásobou 400 kg písku.
Hlavní trakční alternátor je třífázový stroj typu Siemens Drásov 1FC2 454-4, pomocný trakční alternátor je typu Siemens Drásov 1FC2 282-4. Trakční usměrňovač hlavního motorgenerátoru je třífázový polořízený v můstkovém zapojení, typu Lokel RTU 1. Usměrňovač pomocného trakčního soustrojí je třífázový neřízený, v můstkovém zapojení, typu PSU M150 B6U 660/884 od firmy Semic Trade. Po usměrnění proudu vyrobeného alternátorem jsou napájeny čtyři stejnosměrné sériové čtyřpólové trakční elektromotory TE 005 E. Regulaci motorgenerátoru zabezpečuje mikroprocesorový řídicí systém INTELO Maxi od ostravské firmy Lokel. Toto zařízení kromě regulace přenosu zajišťuje buzení pomocných alternátorů, automatickou regulaci rychlosti, diagnostiku lokomotivy (i dálkově prostřednictvím sítě GSM), mazání okolků, pískování, řízení brzdových systémů, ochranu proti skluzu a mnohočlenné řízení. Lokomotiva disponuje výkonnou elektrodynamickou odporovou brzdou, která pracuje ve spádovém nebo zastavovacím režimu. Její ovládání je stupňovité, řízení brzdy zprostředkovává mikroprocesorový regulátor. Blok EDB je spolu s elektrickým rozváděčem uložen v zadním (kratším) představku. Motory pomocných pohonnů jsou asynchronní, řízené pulsními měniči. Napětí palubní sítě je 24 V. Lokomotiva je vybavena zásuvkami pro napájení sítí přípojných vozů a disponuje ovládáním dveří těchto vozů. Na stanovišti strojvedoucího jsou rychloměrné soupravy Metra LTE. Lokomotiva je vybavena vlakovým zabezpečovačem LS 90 od firmy AŽD Praha.