Sewage sludge amendment of soils leads to an increase in soil fertility, but may induce heterogeneities not initially present in the soil. Spatial variation of soil organic carbon (C) and nitrogen (N) was studied in a heavy clay soil after a sewage sludge application and NPK-treatment (nitrogen, phosphorus, and potassium) using geostatistical approaches. In total, 314 soil samples were taken on two adjacent 40 m × 40 m plots (one sludge-amended and one NPK-treated) at three different scales (scale 40 m: 40 m × 40 m, scale 10 m: 10 m × 10 m, and scale 2.5 m: 2.5 m × 2.5 m). The coefficient of variation almost doubled for both C and N after sludge treatment. Because of this, more samples were needed to estimate mean values for the sludge-amended plot compared with the NPK-treated plot. To estimate the population mean at the 95% confidence level with 10% uncertainty (for all scales and all treatments), 5 to 13 samples were required for C and 4 to 7 for N. The C was spatially more structured compared to N. Semivariances of the sludge-amended plot displayed higher values compared with the NPK-treated plot, except for N at the smallest scale. This was probably due mainly to the sludge characteristics and the application technique of the sewage sludge. Constant semivariance (sill) was reached at ranges up to 15 m for C, but it was often unbounded (>40 m) for N.