Prior to entering provincial politics, Cullen served federally as a member of Parliament (MP) representing the riding of Skeena—Bulkley Valley from 2004 to 2019.

Born and raised in Toronto, Ontario, Cullen worked in several countries in Central and South America, during the 1990s, on community economic development projects.

[5] He moved to Smithers, British Columbia in 1998 and started a private consulting business focussed on strategic planning and conflict resolution.

[19][20] He also spent time lobbying the Liberal government to publicly disclose the bids for Ridley Terminal; the proposed sale of the Prince Rupert Port Authority coal loading terminals by the federal government to a private firm was criticized by opposition parties as undervaluing the facility and likely to restrict fair access by competing coal companies.

[22] In the 2006 election, Cullen faced a strong challenge from the Conservative Party candidate and former MP Mike Scott (who had represented Skeena from 1993 to 2000).

Two winners are picked each year and are flown to Ottawa to watch their submissions introduced in the House of Commons as private member's bills.

[38] The 2013 Hill Times Annual Most Valuable Politician & All Politics Poll awarded Cullen 3rd place in the "Best Up-and-comer MP" category, tied with Elizabeth May.

[43][44] Cullen proposed that joint primary nominations should take place in Conservative-held ridings to determine the best possible local candidate to avoid vote splitting among 'progressives'.

In his policy papers thus far, Cullen has also advanced a number of other ideas such as: creating a national public transit strategy, instituting carbon cap-and-trade pricing, putting a moratorium on new genetically modified organisms, redefining the Canadian Wheat Board, and holding a referendum on voting reform (Cullen supports mixed-member proportional representation as currently used in New Zealand and Germany).

Whereas at the beginning of the race Cullen was considered one of the "also-rans", he eventually was given considerably more attention, with the CBC, The Globe and Mail, Toronto Star, and National Post all running articles on his candidacy.

[56] In March 2015, Cullen attacked Joe Oliver over his avoidance of Question Period after repeated delays in introducing the budget after the drop in oil prices.

[58] As part of the Take Back Our Coast campaign, Cullen toured dozens of communities around British Columbia's north, interior, lower mainland and across Vancouver Island promoting Bill C-628 and raising awareness about the potential impacts of a pipeline or supertanker spill from Northern Gateway on fisheries, tourism and communities.

Cullen's appointment came in the midst of the 2020 Canadian pipeline and railway protests, after the hereditary chiefs refused to meet with BC Minister of Indigenous Relations Scott Fraser.

[67] His candidacy became the subject of controversy when he was acclaimed by the party one week after Annita McPhee, a former elected president of the Tahltan Nation, announced she was seeking the nomination for the riding.

[68] The BC NDP has an equity policy whereby a male MLA has to be replaced by a member of an equity-seeking group, such as a woman or a First Nations person, when he retires.

The party claimed that McPhee's application contained invalid signatures, and that the local riding association conducted a search for candidates to meet its equity policy but none were willing to stand.

[71] On November 26, 2020, Cullen was sworn in to the Executive Council of British Columbia as Minister of State for Lands and Resource Operations.