Po kilkutygodniowym okresie przejściowym objął 12 grudnia 2003 fotel premiera Kanady.
Premier Paul Martin w swym inauguracyjnym wystąpieniu przedstawił program na najbliższy okres. Główne jego elementy to prowadzenie liberalnej, prowzrostowej polityki gospodarczej, redukcje redystrybucji dochodu narodowego oraz dalsza redukcja długu budżetowego i poprawa stosunków z USA, nadszarpniętych w ostatnich latach rządów poprzednika.
W wyborach parlamentarnych, które odbyły się 28 czerwca 2004, partia Martina wygrała, zdobywając 36,7% głosów i 135 mandatów poselskich (z 308)Oficjalne dane ze stron agencji Elections Canada (dane z 2004).. Pozwoliło jej to na utworzenie rządu mniejszościowego. Był to pierwszy kanadyjski rząd mniejszościowy od 1980.
W listopadzie 2005 parlament uchwalił wotum nieufności wobec jego rządu, co spowodowało przedterminowe wybory parlamentarne przeprowadzone 23 stycznia 2006. Wybory wygrała Partia Konserwatywna, która zdobyła największą liczbę mandatów (124 z 308) i dzięki temu mogła utworzyć rząd mniejszościowy.