The former Chesterfield first team coach replaced Ashley Hoskin as manager in October 2015.
But the Seagulls managed four league wins under Lynch and are nine points from safety with eight games remaining.
"We thought he was the man for the job but unfortunately it didn't work out," Bay chairman Dave Titchiner said.
Captain Carl Rodgers and Luke Denson will be in charge for Thursday's home game against Mickleover Sports.
Colwyn Bay were relegated from the Conference North at the end of the 2014-15 season.

Both the Islamic State group (IS) and Kurdish militants have claimed a number of attacks in Turkey in recent months.
Turkey is part of the US-led coalition against IS, and coalition planes use its air base at Incirlik for raids in Iraq and Syria.
Turkey is also conducting a campaign against Kurdish militants.
How dangerous is Turkey's unrest?
Tears and destruction amid PKK crackdown
Turkey in midst of hideous vortex
A ceasefire between the government and the Kurdistan Workers Party (PKK) broke down last year.
On Saturday an emergency travel warning was published on the website of the US embassy in Turkey.
"There are credible threats to tourist areas, in particular to public squares and docks in Istanbul and Antalya. Please exercise extreme caution if you are in the vicinity of such areas," it read.
Antalya, on Turkey's Mediterranean coast, is a major tourist centre visited by millions of people every year.
The warning comes a day after Israel's counterterrorism bureau urged all Israelis to avoid Turkey, saying: "There are immediate risks of attacks being carried out in the country, and we stress the threat applies to all tourism sites in Turkey."

Thomas Buckett, now 21, fell 15ft (4.5m) through a skylight at Clayton Hall Business and Language College, Staffordshire, in May 2010.
He shattered one side of his skull and was in a critical condition for two weeks.
A compensation claim launched by his family was thrown out on Monday.
Judge Main QC heard Mr Buckett had been left with "a legacy of significant physical, intellectual and behavioural dysfunction" but found that the injuries "arose directly from his own actions".
He heard Mr Buckett was part of a group of youths that had earlier broken into the college and engaged in "vandalism, criminal damage and dishonest criminal behaviour", including stealing items from the tuck shop.
The judge, sitting at Telford County Court, concluded the group had moved on to explore part of the roof and Mr Buckett had probably jumped down on to the skylight, "thinking it would hold his weight and not with the intention of breaking it".
While criticising a Staffordshire County Council risk assessment and saying such a trespass incident should have been foreseen, Judge Main found in favour of the authority and dismissed the claim.
The Buckett family has declined to comment.
Their solicitors described the judge's ruling as "extremely disappointing".
Dianne Yates, partner at Birchall Blackburn Law, said the judge had dismissed legal arguments in respect to the "criminal behaviour", but had not been able to award damages due to case law.
"Thomas has suffered life-changing injuries and the family is now looking at how they can ensure he has sufficient care going forward," she said.
In a statement, Staffordshire County Council described it as a "terrible incident" that had "a profound and life-changing impact on Thomas and his family".
"However, our decision to defend this case was about fairness to the taxpayer," council chief executive John Tradewell said.
He said it was not fair for public money to be used for compensation under these circumstances.
"The county council will continue to help Thomas access the care and support he needs to live as fulfilling a life as possible."
The family was ordered to pay £150,000 costs.
Evo-Stik Northern Premier Division strugglers Colwyn Bay have sacked manager Kevin Lynch following Easter Monday's 3-0 home defeat to Marine.
[NEXT_CONCEPT]
The US has warned its citizens of "credible threats" to tourist areas in Turkey, particularly in Istanbul and the southern resort city of Antalya.
[NEXT_CONCEPT]
The family of a teenager left with severe head injuries after a roof fall has been ordered to pay £150,000 after losing a compensation claim.