Värdarna hade tagit en tidig ledning när Tom Cleverley körde i ett lågt skott.
Men Evertons defensiva svagheter dök upp igen inom några sekunder när Marc Pugh utjämnade för Cherries.
Baines slog från vänster om lådan för att försegla en första liga seger i nio matcher för Toffees men några hemma fans protesterade mot Martinez.
Återupplev Evertons seger här.
Följ alla reaktioner på lördagens fotboll här
Den winless strimma i ligan, tillsammans med förra helgens FA Cup semi-final nederlag av Manchester United, hade väckt betydande missnöje bland Everton fans om sin spanska chef.
Ex-Wigan manager hade sagt att han var "redo att slåss mer än någonsin" i uppbyggnaden till matchen, en vecka efter en sista minuten förlust på Wembley som själv följde en 4-0 ödmjuk av Liverpool.
En banderoll som sa "Dags att gå Roberto" flögs över marken under matchen, och ett antal anti-Martinez banners sågs i Goodison Park.
Cleverleys mål från kanten av straffområdet och Bournemouths snabba utjämning visade det goda och dåliga i Evertons strategi.
Uppbyggnaden till och verkställandet av den tidigare Manchester United midfielders ansträngningar visade vilken typ av snygg, attraktiv fotboll som Martinez är känd för att uppmuntra.
Men inom några sekunder spelet var helt fyrkantig, Callum Wilson skaka Premier League debutant Matthew Pennington av bollen innan sätta i ett kors som hemmaförsvaret misslyckades med att ta itu med, vilket gör att Pugh att slå.
Positiviteten hos den tidiga ledningen försvann snabbt, men det var inte förrän nära halvtid som några knotande av missnöje hördes runt en dämpad Goodison.
Hemmalaget var på framfoten från tidigt i andra halvlek, men efter att ha regenererat ledningen fick de flera nervösa ögonblick av en spiriterad Bournemouth.
Substitute Benik Afobe missade en rubrik från nära håll, och Wilson krävde ett straff efter en sammandrabbning med John Stones.
Det kändes inte som en Everton-föreställning att svara tvivlarna.
Mediauppspelning stöds inte på den här enheten
För Bournemouth var det en tredje på varandra följande nederlag och ett resultat som lämnade dem nio poäng och fyra platser ovanför nedflyttningszonen med två matcher att gå.
Cherries kan se tillbaka på sin första säsong i toppflygningen med lite stolthet, men trots att spela attraktivt ibland på Goodison, detta var en femte förlust i deras senaste sex utflykter.
Endast Newcastle och Aston Villa har medgett mer än de 63 som Eddie Howes sida har släppt in, och Bournemouth manager kommer att ruska hur Everton tilläts återta ledningen.
Aaron Lennons kors hängde hela vägen över Bournemouths ask innan Baines med eftertryck konverterade den.
Mediauppspelning stöds inte på den här enheten
Margaret Aspinall, ordförande för Hillsborough Family Support Group, och Jenni Hicks var bland flera släktingar till offren för katastrofen 1989 som presenterades för publiken strax innan kick-off med Mrs Aspinall omfamna Martinez på peklinjen.
Kampanjdeltagarna fick en lång ovation av publiken i slutet av en känslomässig vecka för staden Liverpool efter en undersökning drog slutsatsen att de 96 fans som dog hade dödats olagligt.
Everton boss Roberto Martinez: "Segern var mycket viktig - det har varit en känslomässig tid. Vi var tvungna att vinna. Vi var tvungna att gräva djupt, vi visade att vi är ett team och att vi har karaktär.
På Everton fans protesterar om hans regeringstid: "I fotboll måste du koncentrera dig på att påverka spelet och bara vinna. Den vinnande känslan låter dig gå vidare. Det är vad vi kan ta från idag.
"Dessa aspekter (fans som organiserar banners som ska flygas över Goodison) är inte för mig. Min koncentration förbereder spelarna och förbereder sig för spelet."
Mediauppspelning stöds inte på den här enheten
Bournemouth manager Eddie Howe: "Jag tycker att vi var värda ett drag, de två mål vi medgav var ur sitt sammanhang.
"Vi var solida och vår väktare var en åskådare för större delen av spelet. När chanserna kom var vi inte tillräckligt kliniska."
Everton besöker Leicester nästa lördag (17:30 BST), som kan vara en titelvinnande fest för Foxes, medan Bournemouth värd West Brom (15:00 BST).
Matchen slutar, Everton 2, Bournemouth 1.
Andra halvlek, Everton 2, Bournemouth 1.
John Stones (Everton) vinner en frispark i den defensiva halvan.
Foul av Lewis Grabban (Bournemouth).
Hörnet, Bournemouth. Förföljd av Matthew Pennington.
Hörnet, Bournemouth. Förföljd av Leighton Baines.
Försök missade. Matt Ritchie (Bournemouth) vänster fotade skott från utsidan lådan är nära, men missar till höger. Hjälpt av Benik Afobe.
Substitution, Everton. Kieran Dowell ersätter Ross Barkley.
Försök blockerat. Junior Stanislas (Bournemouth) höger fotade skott utanför lådan är blockerad. Hjälpt av Charlie Daniels.
Handboll av James McCarthy (Everton).
Ersättning, Bournemouth. Lewis Grabban ersätter Callum Wilson.
Försök missade. Benik Afobe (Bournemouth) huvudet från mitten av lådan är bara lite för hög. Hjälpt av Callum Wilson med ett kors.
Försök missade. Junior Stanislas (Bournemouth) höger fotade skott från vänster sida av lådan är hög och bred till höger. Hjälpt av Andrew Surman.
Utanför, Bournemouth. Matt Ritchie försöker en genom boll, men Simon Francis fångas offside.
Hörnet, Bournemouth. Förföljd av Darron Gibson.
Försök missade. Tom Cleverley (Everton) höger fotade skott utanför lådan missar till höger. Hjälpt av Ross Barkley.
Försök blockerat. Matt Ritchie (Bournemouth) vänster fotade skott utanför lådan är blockerad. Hjälpt av Benik Afobe.
Försök blockerat. Junior Stanislas (Bournemouth) höger fotade skott från vänster sida av lådan är blockerad.
Försök blockerat. Benik Afobe (Bournemouth) vänster fotade skott från mitten av lådan är blockerad. Hjälpt av Simon Francis med ett kors.
Offside, Everton. Leighton Baines försöker en genom boll, men Romelu Lukaku fångas offside.
Ersättning, Bournemouth. Benik Afobe ersätter Joshua King.
Ersättning, Bournemouth. Junior Stanislas ersätter Marc Pugh.
Försöket räddades. Tony Hibbert (Everton) höger fotade skott från höger sida av lådan sparas i mitten av målet. Hjälpt av Ross Barkley.
Försöket räddades. Aaron Lennon (Everton) höger fotade skott från utsidan boxen sparas i mitten av målet. Hjälpt av Darron Gibson.
Mål!  Everton 2, Bournemouth 1. Leighton Baines (Everton) vänster fotade skott från mitten av lådan till övre vänstra hörnet. Hjälpt av Tom Cleverley.
Försöket räddades. Matt Ritchie (Bournemouth) vänster fotade skott från utsidan rutan sparas i nedre högra hörnet.
Darron Gibson (Everton) visas det gula kortet för en dålig foul.
Foul av Darron Gibson (Everton).
Matt Ritchie (Bournemouth) vinner en frispark i anfallshalvan.
Substitution, Everton. Romalu Lukaku ersätter Oumar Niasse.
Försök missade. Callum Wilson (Bournemouth) höger fotade skott från höger sida av lådan är nära, men missar till höger. Hjälpt av Simon Francis.
Försök missade. Joshua King (Bournemouth) höger fotade skott från utsidan lådan är nära, men missar till vänster. Hjälpt av Callum Wilson.
Försök blockerat. Ross Barkley (Everton) höger fotade skott utanför lådan är blockerad. Hjälpt av Leighton Baines.
Försening över. De är redo att fortsätta.
Försening i match Steve Cook (Bournemouth) på grund av en skada.
Hörnet, Everton. Sammankallad av Simon Francis.
Oumar Niasse (Everton) vinner en frispark i anfallshalvan.
Foul av Matt Ritchie (Bournemouth).
Försök missade. Joshua King (Bournemouth) höger fotade skott från höger sida av lådan missar till höger. Hjälpt av Callum Wilson med ett nyckelkort.
Tom Cleverley (Everton) vinner en frispark i den defensiva halvan.
Leighton Baines fick vinnaren mot Bournemouth att göra slut på Evertons dåliga lopp och lätta på trycket på chefen Roberto Martinez.