NOTE: A great spoiler sent in by MW.

The film begins with a voiceover of Frank Costello (Nicholson) explaining that he doesn't want to be the product of his environment, he wants his environment to be a product of him.  As he's speaking, grainy historical footage plays of violent riots taking place in the film's setting, Boston.  Costello continues to speak in his half-Boston/half-Jack accent, and he is crude, crass, like all the characters proudly Irish, and unapologetically racist.  He explains that what annoys him about African Americans is their refusal to realize that they won't be given anything.  Costello's belief is you have to do whatever possible to take what you want.

We first see Costello in a scene in a small convenience store where he collects money from the owner.  The shop owner is visibly unnerved by Costello, and Costello warns him to have more money for him the next time.  There's a small boy at the counter watching the exchange.  The shop owner's teenage daughter is behind the counter, and Costello asks if she's got her period yet.  His attitude is nonchalant and all the more threatening for it.  The daughter is both affronted and compelled by the powerful Costello (she answers his rhetorical question), and of course the shop owner doesn't express any emotion about what he's hearing.  Then Costello takes notice of the young boy, who will grow up to be Colin Sullivan (Damon).  Costello confirms the boy's identity, and then demands (without demanding) that two full bags of groceries be filled for young Sullivan.  Costello gives the boy some change and tells him there's more money to be had if the boy works for him.

Either a little before or a little after this scene we see Costello with the only man he trusts, his second in command Mr. French (Ray Winstone).  French and Costello execute a pair of women at a shoreline.  The murders are quick and cold, and Costello remarks that the body of the second girl "fell funny."

We see Sullivan show up at Costello's, and we learn that the boy is smart.  He can recognize a passage of James Joyce Costello has quoted.  Costello explains to the boy that when you've got a gun pointed at you, it doesn't really matter whether you're a cop or a criminal.

And so we see the grown up Sullivan training to be a police officer.  Close to this point Billy Costigan (DiCaprio) enters the film.  Costigan is also training to be a police officer, though the two men are not being trained together and so haven't met.  They are both serious and ambitious, as we see in a training montage, though it appears that Sullivan has it in him to succeed more than Costigan.  Costigan has a friend throughout training called Brown (important later).  And, in keeping with the symmetry of the two lead characters that continues through the film, Sullivan has a friend who will become his partner, Barrigan (also important, naturally).  There is a football game that the cops lose to the firemen, and Sullivan can't stand losing and calls the firemen homos, among other things.  Barrigan tries to talk to Sullivan after the game a little personally, but Sullivan only remarks again on the firemen being homos.  When Sullivan graduates, Barrigan remarks that Sullivan's on the fast track already, heading towards the division of the police that's undercover.  Barrigan asks if Sullivan will go out to celebrate, but Sullivan has spotted Costello and goes to speak to him.  Costello remarks that school's out, no more books, and gives Sullivan a present.  Sullivan seems genuinely grateful to his boss/father-figure; we don't see what the gift is, but my guess is it's a mean looking knife that appears later in the film.

We see some of Costigan's life.  Costigan's father died, and they didn't have too close a relationship.  Costigan's mother was dying of cancer, and Costigan's Uncle confronts him about becoming a police officer.  Costigan is hostile to his mother's brother and explains that when she dies, their connections are over.  So Costigan, before joining the academy, is without family or friends.  At Costigan's mother's funeral, Costigan picks up a Saint card mentioning the dear departed, and sees Costello's name signed below it.  It appears Costigan's uncle associated with Costello, and that Costigan grew up where he might have joined a criminal gang, but has been working to avoid it. 

Next we meet Queenan (Martin Sheen) and Dignum (Mark Walhberg).  Queenan is the chief of the special unit, and Dignum the first/staff sergeant.  Queenan is good cop, another father figure opposite to Costello, and Dignum the belligerent bad cop, who speaks abusively partly because he enjoys it, mostly because, as Queenan says, "it's his own style," and he can assess a man by the way he responds to his abuse.  Sullivan is invited in and because of his record is welcomed to the service.  He ignored Dignum.  As Sullivan leaves, Costigan enters, noticing how the receptionist responds to Sullivan, who is flush with success.  Costigan is given a much harder time, and you can see in his eyes that he's having a hard time withstanding Dignum's attacks on his character.  Queenan and Dignum belittle Costigan, saying he has a violent past and no family, and isn't cut out to be a police officer.  They are doing this for a reason: they want him to go undercover and join Costello's crew.  Queenan asks him to do it for him.  The threat is that he'll be nothing as a police officer unless he agrees.  But they also know that Costigan's smart, got 1400 on his SATs and should be "an astronaut, not a Statie."  Costigan quotes Hawthorne, to which Dignum replies, "What, you don't know any Shakespeare?"  Costigan finally agrees, and we see that he's been kicked out of the academy and sent to prison, where he's recognized as having a criminal cousin.

Sullivan is doing well and finds a spacious apartment that overlooks the State Capitol's golden dome.  At work, we meet Ellerby (Alec Baldwin), who is the normal police chief, and doesn't have access to the undercover detectives of Queenan's unit, though he would like to (as would Sullivan.)  Their job is to go after Costello, who they believe to have stolen computer chips used in missiles.  Sullivan works directly under Ellerby. 

When Costigan gets out of jail, he looks up his cousin and swears he's not a cop.  His cousin gets him involved in drug deals.  His cousin has dealings with Mr. French, and Costigan comes along to a bar where they meet.  Costigan orders a cranberry juice so that the thug at the bar comments on Costigan's having his period.  Costigan smashes a glass over the thug's head, which caused Mr. French to back Costigan against a wall and warn him that he can't touch any of his crew, and that he was lucky that the thug wasn't "a guy you're not allowed to touch."  Mr. French knows of Costigan's family, and beats on the thug himself for not knowing who Costigan is.  We see that Costigan is unnerved by both his actions and the menace of Mr. French, but he keeps his cool.

Later, Costigan is eating at a similar convenience store/deli as the one at the start of the film.  The owner is being harassed by two of the Italian mafia from Providence.  Costigan beats both men badly, breaking his hand in the process.  Later, Costello sits next to Costigan in a bar.  Costigan professes not to know Costello.  Costello takes him into a back room with Mr. French, and while they shake him down checking for weapons or a wire Costello says it's possible Queenan would have sent him, so he has make sure.  Mr. French breaks open Costigan's cast and Costigan screams in pain, then Costello beats Costigan's broken hand with Costigan's boot, asking him if he's a cop.  Finally, Costello is convinced Costigan's not.  He explains to Costigan that either Costigan's going to be killed by the Italian mafia, or he will work for Costello and gain Costello's protection.  Costigan acts like he doesn't know he can't handle the situation himself, and Costello and French exchange a look.  They tell Costigan not to do stupid drug deals with his idiot cousin anymore.

We see Sullivan at a crime scene looking over the bodies of the two dead mafia men.  Sullivan's friend Barrigan joins him.  Barrigan and Brown will be part of Sullivan's personal task force.  Sullivan has at this point met a woman on an elevator and flirted with her, then taken her to dinner.  She's taken with his charm, which has come with his success, and at dinner is further impressed with his intelligence.  They joke over a ridiculous French dessert.  Her name is Madolyn (Vera Famiga). 

Costigan begins to go along with Mr. French on small deals, usually shaking down people who owe them money.  At one point Costigan thinks a bookie is going for a gun, and knocks his teeth out.  French sees that it was just a pack of cigarettes.  Afterwards, French and Costello chastise Costigan, but they don't really care about the bookie's teeth, and are probably impressed with Costigan's action.  Costigan is playing it a bit clueless, like he's got a lot to learn about being a gangster, and is therefore impressionable and not a threat.  He is so shocked when he first witnesses Mr. French kill someone that he can't hide it.

About Costello: he's obviously cruel, and doesn't express emotion about the grisly things he does.  After killed the mafia men, Costello severed one of their hands and waved it in front of Costigan, speaking about John Lennon.  Costigan is frightened, and immediately gets out of the room to toss the wire he's wearing out the window.  He explains to Queenan that he's going to do this by phone from now on, he'll never wear a wire again.  Costello has a mistress, who is perhaps a nun or used to be.  Costello doesn't have an heir, but wants one—we see his mistress reading a book about getting pregnant.  There isn't much shown of Costello's sex life, but throughout we get the idea that he's having sex anytime he isn't killing someone or scaring someone. 

Costigan meets angrily with Queenan and Dignum.  He's done undercover for a year and he's had enough, he's starting to crack from the pressure.  They remind Costigan that no one knows his identity except them.  Dignum says all he has to do is erase Costigan's file and Costigan will be just another member of Costello's crew, and can be arrested and charged for the crimes Costello committed when Costigan was there.  Costigan hits Dignum, which Dignum appears to respect.  Again, Queenan tells him in a fatherly way to hang in there. 

At some point one of Costello's crew is arrested, and Sullivan goes in with the camera's off to tell him to call "his mother" with the code "I won't be able to make it to dinner."  This is to tip Costello, who answers, that the cops are onto his coming deal with Chinese buyers of the computer chips they'd stolen. 

Sullivan is surprised to find that there's a setup involving the FBI and cameras to trap Costello at the deal.  He wasn't told because Dignum was getting the information from Costigan.  Luckily for Sullivan, the cameras aren't placed properly and they can't see the deal.  Both Sullivan and Costigan text message their superiors about what is going on, and at this point both men suspect that there is an informant on the other side.  The deal happens, but it's not the computer chips, just some light fixtures.

Costigan, in a panic, calls Dignum and asks him to start giving out false information about a wiretap to see if Costello learns about it, to narrow down what department the informant is working in.  Dignum doesn't take him too seriously. 

About Madolyn: she is the department psychiatrist, who treats policemen.  Her relationship with Sullivan grows until she prepares to move in with him, which she eventually does.  When she begins bringing personal items to Sullivan's apartment, Sullivan teasingly but seriously tells her that such items belong in the bedroom if anywhere at all, and not in the living room.  He prefers the past be forgotten, even a cute picture of Madolyn as a small child.  Sullivan and Madolyn, though together for months, appear to have trouble in the bedroom.  She tells Sullivan it's not a big deal, suggesting Sullivan is impotent, which probably has to do with the stress Sullivan is under.  At the same time she receives a visit from Costigan, who of course does not reveal his identity to her though he'd probably like to tell someone, anyone.  He demands pills which she eventually gives him, and ultimately Costigan moves on to Oxycotin that he takes three or four at a time to help him deal with the increasing stress of assignment.  Madolyn tells Costigan she's reassigning him to another psychiatrist after his treatment of her, and so Costigan asks her out for a drink.  She is attracted to his vulnerability, let's say, and so agrees, and they have a discussion at a bar about lying, and Costigan gets it out of her that she would lie to "keep an even keel," that lying is sometimes necessary if it works to a greater good.  Eventually, Costigan shows up at her apartment needing to talk to someone, just as she's preparing to move into Sullivan's.  Costigan finds the picture of her as a girl, and takes it from its packing box and hangs it back on the wall, which charms Madolyn.  She remarks that his vulnerability is "freaking her out," but the pair wind up kissing and then making love.  When Costigan eventually returns to see her again, though, she tells Costigan that she can't be a friend to him.  Costigan appears to understand.

Sullivan has ironically been assigned the task of finding the rat.  Basically, he has to find himself.  He instead calls Costello and asks him to gather the social security details and real names of his crew so that he can look them up in the police computer.  Costello is indignant, and Sullivan has to talk him into it. 

Costigan, meanwhile, realizing he has to find the police rat himself, has decided that if he follows Costello, that eventually he'll find the informant talking to Costello.  Costello at one point "interviews" Costigan about the possibility of his being the rat, and Costigan tells Costello again that he's not a cop.  At this point Costello appears unhinged, a bit insane, a bit unfocused.  He appears to feel like a king who is being threatened, and says "heavy lies to crown."  He suggests that Costigan wants to take his place, and Costigan dissuades him of this idea, but Costello lets Costigan know he's not off the hook, that he's still under suspicion.  Costello and French feed Costigan some false information, but Costigan is too smart to feed it to Queenan and Dignum, and after that French declares that "it's not Costigan."  Later Costigan finds Costello covered in blood from his hands to his elbows, and French remarks that not all of their crew answered his questions the way they were supposed to.  Costigan is a complete mess at this point, frightened for his life, sure that he'll be found out if he doesn't find his opposite on the other side.

There is a scene where Costello's crew is rounded up to write down their information for Costello.  One of Costello's men spells "citizens" wrong and Costigan crosses it out and writes it correctly.  After this, Costigan leaves instead of staying put as he's been ordered to.  Costigan waits for Costello, and follows him to a porno theater where Sullivan is waiting.  Costello pretends to be jerking off, and startles Sullivan with a ridiculously large dildo sticking out of his pants.  Costello explains that he owns the theater and that's why it's safe for them to meet.  Sullivan notices Costello is extremely paranoid, and tries to calm him down and reassure him that he needs to trust Sullivan, that he, Sullivan, is great at lying, and wouldn't be good at his job if he wasn't completely loyal to Costello.  Meanwhile, Costigan is watching this from a few rows back, but can't see Sullivan's face.  But he sees Costello give Sullivan the envelope that he'd written "citizens" on.   

When Sullivan leaves the theater, Costigan attempts to follow him.  At one point Costigan's cell phone rings and this alerts Sullivan, who runs ahead into an alley and crouches behind a delivery truck, taking out the mean little knife—which isn't so little.  Costigan's cell has a message to arrest the man he's following.  As Sullivan is crouching, footsteps approach.  Sullivan turns the corner and stabs without looking.  It's not Costigan he's killed but a man making a delivery.  Sullivan runs.  Costigan sees the man Sullivan has killed and continues pursuit, but Sullivan has gone.  Just before Sullivan disappears, he looks back from the middle of a street and sees a traffic camera.  The first thing Sullivan does is return to the police station to access this camera.  His suspicious is right: there was a man following him.  But just as Costigan was unable to make out Sullivan's face, Sullivan is unable to recognize Costigan's face from the camera image.  But Sullivan gets the idea from Costigan, which he overheard, that if you follow the boss you'll find the rat who takes his orders from the boss.  Since he is in charge of finding the rat, he orders police officers to tale Queenan, saying he has to follow any lead, no matter how ridiculous. 

Earlier, Costigan heard a comment from one of Costello's men about Costello being an FBI informant.  Costigan shoots the man in the knee until the man says he's noticed that a lot of the people Costello doesn't have a use for anymore wind up being captured by the FBI.  Costigan takes this information to Queenan, who he waits for outside his house.  Queenan invites him in and they have a fatherly conversation, and it appears that Queenan has some genuine feeling for Costigan, despite the manipulative good-cop vibe of earlier fatherly talks.

Later on, Costigan asks Queenan to meet him at an abandoned building, and Queenan agrees, unaware that he's being followed by Sullivan's men.  When Sullivan confirms the location, he calls Costello's men and they rush to the spot.  They angrily call Costigan, asking where he is, and giving Costigan the address to the location—only, it's the wrong address.  Costigan runs down the fire escape while Queenan distracts Costello's men.  When Sullivan's cops see Costello's men enter the building, they are surprised and think that Queenan must indeed be the rat who is meeting with them.  Then we see a body falling through the air.  The body lands with a splat of blood just in front of Costigan.  Costigan can't believe he's looking down at Queenan's dead body.  Costello's men arrive and Costigan explains he's just got here.  They are angry he is late, and retreat to their vehicle to leave the scene.  Sullivan's men have noticed a body has fallen off the building, and want Sullivan's orders.  Sullivan says to stay in the car.  They refuse to do so, though, and a shootout ensues.  One of Costello's men is shot, as is one of the cops. 

When they return to their hideout, Costigan has to explain why he wasn't there on time.  He says he was at the grocery store.  The shot man calls Costigan over, and tells Costigan that he gave him the wrong address, but Costigan was there all the same.  He asks Costigan why he didn't tell anyone, and then he dies. 

We see on the news that the man who died, who didn't tell on Costigan, was an undercover cop.  Costigan is expecting some relief, but Costello just says that the cops are saying he was undercover to throw him off the trail of the real rat. 

Meanwhile, Sullivan is defensive when asked to explain why he asked men to follow Queenan.  Dignum attacks Sullivan, and is relieved from duty for two weeks with pay by Ellerby, his new boss.  Dignum will instead turn in his papers, which means he's either quitting the force or asking to be reassigned.

Sullivan uses Queenan's cell phone to call Costigan.  Costigan hesitates, but, despite everyone in the audience thinking "don't do it, man!" he picks up.  Neither man says anything.  Then Costigan hangs up.  Then Costigan calls back.  This time Sullivan answers, and says who he is, and explains that he's not in charge of undercover.  Costigan hangs up after Sullivan asks him to come into the police station.  Then Sullivan, looking through the rest of Queenan's belongings, finds Queenan's notebook, in which is written what Costigan told him about Costello's possibly being an FBI informant.  Sullivan takes this very seriously.

Costello is off on a deal, and Sullivan calls him to tell him he's being tailed.  Sullivan is upset with Costello, and tells him that he shouldn't have killed Queenan because now he doesn't have access to any information, and the police are out in force and he can't really control them, and that he should lay low for a while.  Costello just yells at Sullivan to get rid of the tails.  Sullivan does this.  He says get rid of the tails because he knows where he's going.  The cops want to know how.  Sullivan says it's because he's been in contact with the informant Costigan.  Costigan does indeed text a message about the location.  So the tails exit and Costello believes he's not being followed, when in fact a multitude of police cars are strategically places to cut off Costello when he arrives.

And Costello arrives, and asks his men to load a shipment of drugs into their trunks.  Costigan is nervous and suggests to Costello that something might be wrong.  When Costello brushes him off, Costigan makes an excuse to "check the back," and runs off just as the cops show up.  The cops have the advantage and use it, peppering Costello's vehicles with bullets.  Mr. French is shot and crashes his car, but Costello gets out of the vehicle as the rest of his men are slaughtered.  Mr. French, his car on fire, shoots himself in the head. 

Costello calls Sullivan, and hears Sullivan's cell phone ringing nearby.  Costello sits on the scoop of a construction vehicle.  He's been shot in the belly.  Sullivan shows himself, and confronts Costello about his being an FBI informant.  Costello admits that he is, but says he only gave up people who didn't matter anymore.  Sullivan is furious, and says that while Costello pretended to be his father that it was all an act, and all because with all the sex and drugs and power he was unable to be a real father, have a real heir.  Costello tries to shoot Sullivan but misses, and Sullivan shoots Costello.  Costello falls into the scoop.  He tries to shoot Sullivan again, and Sullivan curses and shoots a few more times until Costello is dead with arms spread out. 

Sullivan is hailed as a hero back at headquarters, and appears to be on the fast track to becoming head of the department after Ellerby.  Finally Costigan agrees to come in, demanding his identity back.  Sullivan seems convinced that Costigan just wants to return to a normal life, and asks Costigan for his password to access his file.  It's debatable whether Sullivan would have let Costigan go his own way or not, but it doesn't matter because Costigan notices the envelope on Sullivan's desk that Costello gave him: "citizens."  Costigan gets out of the police station immediately.  Sullivan returns to find Costigan gone, and notices the envelope himself.  He rushes to the computer and deletes Costigan's file, so that no one, presumably, knows that Costigan ever existed as a police officer.

Costigan waits outside of Sullivan's apartment, not knowing Sullivan lives there.  He's waiting for Madolyn.  He gives her an envelope and tells her to please keep it safe, unopened, until she hears that he's dead or calls her and asks her to open it.  He apologizes and leaves.  She is tempted to open the envelope, but instead puts it safely in her drawer.  At this point she is pregnant, and shares the news with Sullivan, who is genuinely happy.  With Costello gone, Sullivan is free to have his own life.  What does it matter that he's a cop?  Their child is going to be a boy. 

Sullivan receives a letter from Costigan, but Madolyn sees it first and recognizes Costigan's name.  While Sullivan is in the shower she opens it.  She thinks it's going to be a letter from Costigan about his sleeping with Sullivan's girlfriend, but it's a CD with Costigan's phone number on it.  She puts the CD on and listens with headphones.  It's the conversation that Costello and Sullivan had in the porno theater.  Sullivan appears, and Madolyn rips out the headphone cord so that the conversation plays in the open.  She says, "I thought I was the liar."  Sullivan tries to persuade her that this is just his job, police business, and that it's not what it seems, but she locks herself in the bedroom and Sullivan is too pressed to deal with Costigan to stay and talk to her. 

Sullivan calls Costigan, and Costigan asks him to meet on the same rooftop from which Queenan was thrown.  When Sullivan arrives, Costigan strikes him with his gun.  Costigan lets Sullivan know that Costello made records of all his conversations that he would later give to the FBI if he felt like it—that rat!  Sullivan warns Costigan, but Costigan just beats him and handcuffs him.  Just then Brown arrives.  As we remember from the beginning, Brown was with Costigan at the academy and knows that he used to be a police officer.  Brown is a witness.  He says that Sullivan is the rat and there are bundles of recordings to prove it.  Brown says that might be true, but to lower the gun anyway.  Costigan refuses, but wonders where Dignum is—Brown was supposed to have brought him along.  When Costigan moves into the elevator, with Sullivan asking Brown to shoot Costigan, Brown lets him go, though he is clearly conflicted.  When Sullivan and Costigan are in the elevator, Sullivan finally says "just kill me," which Costigan takes as a sign of his giving up.  And then the elevator doors open.  Blam.  Costigan's head splatters over the back wall of the elevator.  Sullivan can't believe it.  It's Sullivan's old friend Barrigan.  Then Brown makes it down and cautiously inspects Costigan's corpse.  Blam.  Barrigan shoots brown through the head as well.  Then Barrigan explains that Sullivan wasn't the only informant Costello sent into the police force, that he was one too and there may be more besides them.  While he uncuffs Sullivan, he says that Costello was going to sell them both out to the FBI, and that with Costello gone they only have each other. Sullivan, uncuffed, picks up a pistol and steadies himself.  Blam.  Sullivan shoots Barrigan through the head.  Sullivan would rather have his police life than live on the run, it seems.

We see both Madolyn and Sullivan at Costigan's police funeral.  The story is that Barrigan was the rat all along, and that Barrigan killed Costigan and Brown and Sullivan got lucky and shot Barrigan before Barrigan got Sullivan, too.  Madolyn is crying at the funeral, understanding finally what was going on with Costigan all along.  Sullivan attempts to speak with Madolyn, asking about the baby, but she says nothing and doesn't stop walking past him.  At this point the audience can speculate on whose baby it was.  Sullivan had trouble in bed, but Costigan didn't.

The audience can also speculate on what was in the note that Costigan had given Madolyn, since we never see the contents.  What we do see is Sullivan arriving home, opening the door to his apartment, and finding Dignum standing there with plastic wrapped around his feet and hands; it seems logical to suspect that the note asked Madolyn to bring information to Dignum, enough for Dignum to put it all together.  Sullivan says "oh, okay."  Blam.  Dignum leaves the apartment, and the final shot of the film is of a rat creeping along the banister outside of Sullivan's window in such a way that it appears as if it's crawling on the State Capitol in the background.