Both bodies were believed to belong to passengers aboard the crashed jet, Air Force spokesman Col. Jorge Amaral told reporters.
A suitcase containing a plane ticket for the flight, and some other items including a blue-color cabin seat with serial number 237011038331-0 on it, were also found and recovered, said the spokesman.
The items still need verification and confirmation by Air France, the spokesman added.
Air France Flight 447 went missing on Sunday with 228 people onboard, among them 9 Chinese passengers.
Authorities believe there were no survivors in the crash. Col. Amaral on Saturday again ruled out the possibility of finding any survivors.