Ibrahim Abu Naja and Zakaria Agha, along with other top representatives of Palestinian leader Mahmoud Abbas, have been arrested in the Gaza Strip, said officials from his Fatah movement. It is part of a continuing Hamas crackdown, following a coastal bombing last week.
In 2007, when the Islamist Hamas seized control of Gaza, Ibrahim Abu Naja and Zakaria Agha have been appointed by Mr Abbas to run Fatah in the area.
While Hamas has not given a number, Fatah says dozens of its men are being held.
The latest arrests were in response to the detentions of Hamas men in the West Bank, said a Hamas spokesman.
Palestinian president ealier ordered the release of dozens of Hamas members, rounded up by his security forces in the West Bank in the past week. Four men were set free during the day.
In the aftermath of a bomb blast in Gaza a week ago, that killed five Hamas members and a girl, large numbers of each other’s supporters have been arrested by both sides.
Hamas insists the arrests of Fatah members are part of its investigation of the attack in which Fatah denies any involvement. While people were enjoying a day by the sea, the bomb exploded inside a car travelling past a beach.