Foundation and early years Eastern Stars FC were founded in July 2007 following concern from
Milne Bay residents that the lack of clubs in the area had led to many local players joining
Port Moresby-based teams; the club's name is derived from "the star from the East", a symbol that features on the Milne Bay provincial flag.
National Soccer League debut Ahead of the
2008–09 season, it was revealed that Eastern Stars would be one of three new teams joining the
National Soccer League. The side started well, despite their opening match being called off due to heavy rain. They won their opening match against fellow newcomers
Sepik FC 4–3 before a draw with
University Inter and another 3–2 win over
Nabasa United saw them undefeated in their opening three games. Further postponements, plus a draw and a loss in their remaining two 2008 fixtures, saw the side enter the new year in fourth place with eight points, with two postponed fixtures still to be played. However, Stars lost both their games in hand, to
Morobe FC behind them and
Hekari United ahead of them, and the side weren't able to capitalise on their advantage, eventually finishing fifth, just a single point from playoff qualification. The side again registered to take part in the
2009–10 season, bringing in
Solomon Islanders Timothy Joe and
Paul Wale to boost their squad strength. The season saw similar results for Stars: they again finished in fifth position, and this time only a poor goal difference denied them a place in the semi-finals. The club struggled in the first half of the season, having a six-game winless streak between November and January, but managed to win their last five games to soar up the table. They were edged into fifth place by University Inter who had a superior goal difference.
Two Grand Finals The club confirmed their participation in the
2010–11 season in July 2010, with chairman Joseph Ealedona insisting that the club were 'competitive' and would go 'one step further' in the coming season. The side did just that, going into the Christmas break having lost just one game – against Hekari – and even going top of the league for a short time in February, before eventually finishing second in the league table behind the defending champions. After a 3–1 victory over
Tukoko University in the knockout semi-finals, they fell 4–0 to Hekari in the Grand Final after having a man sent off. In October 2011, ahead of the
2011–12 season, the club appointed
Luis Jaime Gomez as its new head coach. Gomez played professional football for
Chilean club
Club Deportivo Universidad Católica in the 1960s and 1970s. Stars made a great start to the 2011–12 season, winning their opening match on 16 October 2011 against Petro Souths FC 7–0 with two goals from Lab Embel. The club won three, drew four and lost two of the next nine games, lying in second place at the league's winter break in December. However, midway through the season Gomez left the club, and franchise owner Joseph Ealedona installed himself as team manager. Eastern Stars eventually finished as league runners–up to Hekari, and were beaten 5–0 by the same team in the league final on 17 April 2012 in front of a 5,000-strong crowd. Stars received
K25,000 for their achievements.
Decline and NSL withdrawal In December 2012, Stars' participation in the
2013 season was thrown into doubt when the NSL board reported that only three clubs had met payment deadlines for the new season; Stars were not among them, and only an additional three places were available in the league despite six other clubs registering their interest. The club finally confirmed its inclusion in the league on 25 January 2013, just one week before the start of the season. Following a mass exodus of players at the end of the 2011–12 campaign, the club appointed former
Papua New Guinea national team assistant manager
Max Foster as its coach for the new season. Stars faced NC Oro in the league's opening fixture of 2013, and despite fielding an entirely new squad from 2012, Stars defeated their opponents 3–1, thanks to a Patrick Aisa brace and a Danny Banaba goal. However, Stars' plight was downhill from then on, and they eventually finished sixth out of the eight teams – the lowest finish since the club's inception. Their final season to date came in
2014, with the side one of seven who had met the requirements for participation. While the side managed an opening day 1–1 draw with defending champions Hekari United on 8 February, the side had to wait until the end of March for a league victory, defeating
Lae FC 2–1 on 22 March. This was to be their only victory all season, with the side finishing dead last with that single win and four draws. In July 2014, it was reported that the side had successfully bid to take part in the upcoming 2015 season. However, ahead of the season kick-off, the side were not one of the seven sides scheduled to compete.
Return to NSL On 1 December 2017, it was reported that the side had once again shown interest in returning to the National Soccer League for the 2018 season. However, on 4 January 2018, franchise owner Joseph Ealedona revealed the side would not be participating, and instead preparing for a return in time for the 2019 season. On 2 January 2019, it was confirmed that the club would be returning to the
2019 National Soccer League. The club was drawn into the Southern Conference and endured a slow start to the season, reaching the halfway stage in 6th place out of eight teams, having won three out of seven games. In the playoffs, they defeated Chebu AROB 2–0, before a 4–1 aggregate defeat to Hekari United saw them enter the third-place match. Against Morobe United, they took a 2–1 lead, but eventually went down 3–2, finishing 4th for the season. The club were expected to take part in the
2019–20 National Soccer League, but they were not one of the final ten teams announced in December 2019. == Honours ==