Petroleum products from leaking underground storage tanks (LUST), from oil spills on clean soils, or from soils surrounding petroleum refineries and crude oil wells could contaminate soil and have the potential to pollute surface and groundwater systems. Removal and proper disposal of petroleum-contaminated soils (PCS) are legally required to prevent further contamination of groundwater. PCS consist of mixtures of natural sands, silts and clays with petroleum products. In Oman, Petroleum Development Oman (PDO) generates approximately 53,000 tons/year of PCS. This research investigated the potential use of PCS in-lieu of natural sand in Portland cement concrete mixtures. The main thrust of the work is to evaluate whether heavy metals will leach out from concrete containing PCS. Raw materials as well as selected optimum mixtures were evaluated for potential contaminants. Two types of PCS were investigated (untreated and treated PCS). For each soil type, six mixtures were prepared by replacing sand with PCS (PCS/sand ratios of 0, 5, 10, 15, 20 and 25%, by weight). A slump test was carried out on fresh concrete. For hardened concrete, compressive and flexural strengths tests were conducted at different curing times of 7, 28, 56 and 90 days. The results indicate that: (1) there is a decrease in compressive and flexural strengths as untreated or treated PCS content increases; (2) for all mixes prepared, the control mixture (0% PCS) yielded the highest compressive and flexural strengths; (3) a target 28-day compressive strength of 30 MPa can be achieved using 25% or less untreated or treated PCS; and (4) treated PCS (less oil content) yielded higher compressive strength results than untreated PCS. Leachability-based testing of PCS inclusion in Portland cement concrete was conducted using an Inductively Coupled Plasma-Optical Emission Spectrophotometry (ICP). Individual raw materials (untreated PCS, treated PCS, water, Portland cement, sand, and coarse aggregate), fresh concrete mixtures containing PCS/sand ratios of 0, 5, 10, 15, 20 and 25%, by weight and hardened concrete samples obtained at different curing periods of 7, 28, 56 and 90 days were a nalyzed for Silver (Ag), Barium (Ba), Cadmium (Cd), Chromium (Cr), Lead (Pb) and Vanadium (V). The results indicate that: (1) the Ag, Cd, Cr and Pb concentrations in the concrete mixes containing treated PCS were consistent with that of the control mix; (2) an increase in PCS content increases both the Ba and V concentration in that mix; (3) Ag and Cd concentrations in concrete mixes containing untreated PCS were consistent with those values obtained for the control mix; (4) the concentrations of Ag and Cd in raw materials were consistent with the concentrations of Ag and Cd in concrete mixes containing untreated and treated PCS; (5) the concentration of Ba was higher in raw materials than in concrete mixes prepared using untreated and treated PCS; and (6) the concentrations of Cr and Pb were lower in raw materials than in concrete mixes containing PCS. Recommendations for further work include conducting durability-based tests such as surface absorption. Furthermore, additional leaching-based tests using the Toxicity Characteristic Leaching Procedure (TCLP) should be conducted to draw a comparison between our results obtained using the Plant Digestion Procedure and those leachability results that could be obtained using TCLP. Such mixes should be also tested for toxic organics concentrations.