Metal-mediated coupling of one isocyanide in cis-[PdCl2(CNR1)2] (R1 = C6H11 (Cy) 1, tBu 2, 2,6-Me2C6H3 (Xyl) 3, 2-Cl-6-MeC6H34) and various carbohydrazides R2CONHNH2 [R2 = Ph 5, 4-ClC6H46, 3-NO2C6H47, 4-NO2C6H48, 4-CH3C6H49, 3,4-(MeO)2C6H310, naphth-1-yl 11, fur-2-yl 12, 4-NO2C6H4CH213, Cy 14, 1-(4-fluorophenyl)-5-oxopyrrolidine-3-yl 15, (pyrrolidin-1-yl)C(O) 16, 3-(3,5-di-tert-butyl-4-hydroxyphenyl)propane-1-yl 17, EtNHC(O) 18] or sulfohydrazides R3SO2NHNH2 [R3 = Ph 19, 4-MeC6H420] led to a series of (hydrazido)(amino)carbene complexes cis-[PdCl2{C(NHNHX)double bond; length as m-dashN(H)R1}(CNR1)]; X = COR2, SO2R3 (21–48, isolated yields 60–96%). All prepared species were characterized by elemental analyses (C, H, N), HR ESI+-MS, IR, 1H and 13C{1H} NMR spectroscopy, and by a single-crystal X-ray diffraction for 38. Complexes 21–48 demonstrated excellent activity as catalysts in copper-free Sonogashira coupling of aryl iodides and a variety of aromatic terminal alkynes. Catalytic system runs in environmentally benign EtOH ensuring product yields of up to 75–96% and TONs of up to 104. Mechanism of the copper-free Sonogashira catalytic cycle involving 21–48 as catalysts was proposed upon identification of key intermediates using HRESI-mass.