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, translated by 47 Church of England scholars at the request of King James, 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." In the general election, Fellure received one write-in vote in Idaho.
He again ran in 2000, and in 2004, challenged incumbent President George W. Bush for the Republican Party nomination. He 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.