In 1992, Fellure filed to run in the New Hampshire, West Virginia and KansasRepublican primaries. By November 1991, he had spent $40,000 of his own money on the campaign, and he sent a King James Bible to the Federal Election Commission as a copy of his platform. Regarding the 1611 English version of the Bible, he said, "God wrote it as the supreme document and final authority in the affairs of all men, nations and civilizations, for time and eternity... It shall never be necessary to change it." He received 36 votes in the New Hampshire primary and complained that President George H. W. Bush and commentator Pat Buchanan were receiving all the media attention.
During the 1996 presidential election while running for the Republican Party presidential nomination, he criticized former President George H. W. Bush as a man "responsible for inestimable damage toward the destruction of this sovereign democratic constitutional republic [who] continued to water the seeds of international, Satanic Marxism to the exclusion of our national sovereignty". He added that President Bill Clinton "merely shifted into overdrive the socialistic, Marxist New World Order agenda." He appeared on the primary ballot in Puerto Rico and received 34 votes (0.01%). In the general election, Fellure received one write-in vote in Idaho.
Fellure again filed to run for president in 2000, but did not appear on any primary ballots. In 2004, he challenged incumbent President George W. Bush for the Republican Party nomination. Fellure was the only candidate to appear alongside Bush in the North Dakota caucus, as he met the Federal Election Commission requirement of $5,000 in receipts. He received 14 of the 2,020 votes cast, and lost all 26 delegates to Bush.