WASHINGTON (CNN) -- The State Department has put a multimillion-dollar bounty on the heads of two Americans who the United States claims belong to an al Qaeda affiliate in Somalia, CNN has learned.

Posters and matchbooks in Somali and English emblazoned with the names and pictures of Omar Shafik Hammami and Jehad Serwan Mostafa tout rewards up to $5 million each for information leading to their arrest or conviction. Both men are on the FBI's Most Wanted Terrorists List.

The rewards are being offered through the State Department's Rewards for Justice Program.

Hammami and Mostafa are members of Al-Shabaab, the al Qaeda affiliate in Somalia, and "have made significant contributions to this terrorist organization's media and military activities," according to a State Department statement on the rewards, obtained by CNN. They are both are believed to be in Somalia and speak English, Arabic and Somali.

A senior FBI official said the United States has information that both men "had a persistent interest in targeting U.S. interests" and are "believed to be involved in planning attacks on U.S. persons or property." But it is unclear what specific attacks against Americans, even ones that have been thwarted, these men have taken part in. Officials said that information is classified.

Hammami, a 29-year-old Alabama native, moved to Somalia in 2006. The State Department claims he joined Al-Shabaab there and received training from Islamic militants, rising through the organization's ranks to command a contingent of foreign fighters. Officials say he was also a "propagandist" for the group, helping to recruit English-speaking youth through writings, rap songs and video statements.

An Alabama court indicted him in 2009 on charges of providing support to a terrorist group.

In July 2011, the Treasury Department placed him on a blacklist prohibiting Americans from doing business with individuals and groups threatening stability in Somalia.

Hammami has been engaged in a public rift with Al-Shabaab over the past year. Last March, he first expressed concern about his safety in an extraordinary Web video. He has since criticized the group's leaders for corruption and living extravagant lifestyles with money fighters collect from Somali residents, and for fighting only in Somalia while ignoring global jihad.

Hammami's family has said they fear for his life.

But the senior FBI official told CNN that Hammami's current status with the group is "immaterial" and that the reward is based on the actions he has already taken to threaten U.S. interests.

"We still believe he is an individual of great significance to the activities that are going on in Somalia with Al-Shabaab," the official said.

Mostafa is believed to be either 27 or 32. He was born in Wisconsin before moving California, where he attended college. He traveled to Somalia in 2005, where officials say he led foreign fighters for Al-Shabaab and served as a media expert and recruiter. He was indicted in California on charges of providing material support to Al-Shabaab.

Al-Shabaab was labeled a foreign terrorist organization by the State Department in 2008. The group was responsible for the July 2010 suicide bombings in Kampala, Uganda, that killed more than 70 people, including a U.S. citizen, gathering to watch a World Cup final soccer match. Al-Shabaab is also believed to be responsible for numerous other attacks in Somalia that have killed international aid workers, journalists, civilian leaders and African Union peacekeepers.

In February 2012 the group's leader, Ahmed Abdi aw-Mohamed and al Qaeda leader Ayman al-Zawahiri released a video announcing the alliance of the two organizations. The Rewards for Justice Program is already offering up to $7 million for information on seven other Al-Shabaab leaders.

Former Secretary of State Hillary Clinton approved the rewards before leaving office. Officials said they hope the rewards will generate new leads from both Somalia and in Somali-American communities in the United States. In addition to the posters and matchbooks, U.S. officials will be talking with local media in Somalia to reach people that may have information about the men's whereabouts.

It is rare for the United States to offer a reward for an American citizen. The most notable previous reward offered for an American was $1 million for Adam Gadahn, who has served as senior operative and spokesman for the core al Qaeda organization.

Officials said that in addition to their leadership roles with a terrorist group, the men are of great interest because of their work trying to recruit other English-speaking youth.

"Anytime we have U.S. citizens who are trying to affiliate with groups to obtain experience and training and have the opportunity to bring back that lethal experience back to the United States, it's a concern," a State Department diplomatic security official said. "There is no question the cases against these two guys are based on their activities to date. However, we have a continuing interest in terrorist activates in Somalia right up to now. And these men serve as very powerful images for radicalization and recruitment."

The new bounties raise the question of what the United States will do with the men once they find them. The Obama administration drew fire from Congress and human rights groups for killing two Americans who belonged to the al Qaeda branch in Yemen. In September 2011, U.S. drone strikes killed Anwar al -Awlaki, a firebrand preacher from New Mexico who began running propaganda for al Qaeda in the Arab Peninsula and rose to become a senior operative in the group, and Samir Khan from North Carolina, who created an English-language Internet magazine for the group

Both officials said the Rewards for Justice Program -- administered by the State Department's Bureau of Diplomatic Security -- is not involved in drone programs and the intent of the reward is to obtain information that will lead to the men's apprehension and prosecution.

"The purpose of the program is to gather information to bring these guys back lawfully," the senior FBI official said. "We want to bring these people before a court."

The Rewards for Justice Program pays large sums of money for information that leads to the arrest or conviction of anyone who plans, commits or attempts international terrorist acts. Earlier this year, President Obama expanded the program to include payments for information about people involved in transnational organized crime or foreign nationals wanted by any international criminal tribunal for war crimes or genocide.

The program has a track record of gaining actionable intelligence. Since its inception in 1984, the program has paid more than $125 million to more than 80 people who provided information that put terrorists behind bars or prevented acts of international terrorism worldwide. The program was central to the capture of Saddam Hussein's sons Odai and Qusai; Ramzi Yousef, convicted of the 1993 World Trade Center bombing; and others.

Under the Rewards for Justice Program, a $25 million reward was offered for information leading to the capture of Osama bin Laden.