Oprané rybí hlavy zbavené očí a žáber s čistými rybími odřezky dáme do studené vody. Přidáme sůl, bobkový list, 3 kuličky nového koření a 6 kuliček pepře. Přivedeme k varu a vaříme velmi pomalu, napůl přikrytou pokličkou, asi 20 minut.
Mezitím cibuli s petrželku nasekáme nadrobno. Na másle zpěníme cibuli, zaprášíme moukou a usmažíme světlou zásmažku. Vmícháme lžičku mleté papriky a 2 malé rajské protlaky. Orestujeme, abychom zbavily protlak kyselosti a zředíme směs scezeným rybím vývarem. Přidáme obrané maso z hlav a nasekanou petrželku. Dochutíme solí a mletým pepřem. Kdo má rád, nechá si kapří hlavy na talíři a obere si je sám.
Makedonskou rybí polévku podáváme horkou s pečivem podle chuti.