Wallace, who won the last of his 18 caps in the pre World Cup warm up game against Scotland last September, replaces the injured Keith Gleeson at open side flanker while, O'Connell, who withdrew from the Ireland team to play Italy with bruised ribs, returns in place of his deputy Donncha O'Callaghan.
O'Callaghan reverts to the replacements bench instead of Gary Longwell.
The Ireland v Scotland game marks the 50th cap for team captain Brian O' Driscoll, while a 64th appearance for second row Malcolm O'Kelly establishes him as the second most honoured player in Irish rugby behind Mike Gibson, who earned 69 caps between 1964 - 79.
The Ireland team to play Scotland in the RBS Six Nations Championship in Lansdowne Road on Saturday, March 27th 2004 at 16.00hrs is as follows:
15 - Girvan Dempsey (Leinster - Terenure College) 14 - Shane Horgan (Leinster - Lansdowne) 13 - Gordon D'Arcy (Leinster - Lansdowne) 12 - Brian O'Driscoll (Leinster - Blackrock College) Captain 11 - Geordan Murphy (Leicester) 10 - Ronan O'Gara (Munster - Cork Constitution) 9 - Peter Stringer (Munster - Shannon) 1 - Reggie Corrigan (Leinster - Greystones) 2 - Shane Byrne (Leinster - Blackrock College) 3 - John Hayes (Munster - Shannon) 4 - Malcolm O'Kelly (Leinster - St. Mary's College) 5 - Paul O'Connell (Munster - Young Munster) 6 - Simon Easterby (Llanelli) 7 - David Wallace (Munster - Garryowen) 8 - Anthony Foley (Munster - Shannon)
Replacements: 16 - Frank Sheahan (Munster - Cork Constitution), 17 - Marcus Horan (Munster - Shannon), 18 - Donncha O'Callaghan (Munster - Cork Constitution), 19 - Victor Costello (Leinster - St. Mary's College), 20 - Guy Easterby (Rotherham), 21 - David Humphreys (Ulster - Dungannon), 22 - Kevin Maggs (Bath).
Not considered due to injury:
Keith Gleeson (Leinster - St. Mary's College), Rob Henderson (Munster - Young Munster), Denis Hickie (Leinster - St. Mary's College), Anthony Horgan (Munster - Cork Constitution), Eric Miller (Leinster - Terenure College), Mike Mullins (Munster - Old Crescent), Alan Quinlan (Munster - Shannon).