Tamper-respondent sensors with random three-dimensional security patterns and methods of fabrication are provided. The method includes establishing a security circuit pattern for a security circuit of a tamper-respondent sensor to enclose, at least in part, one or more components of a circuit board within a secure volume. The establishing includes obtaining in three-dimensions boundaries for the security circuit of the tamper-respondent sensor. The boundaries define a sensor volume within which the security circuit is to reside. The establishing also includes generating at least one trace configuration for the security circuit pattern. The at least one trace configuration defines a random, three-dimensional security pattern within the sensor volume, and the at least one trace configuration establishes, at least in part, the security circuit pattern. The process further includes fabricating the tamper-respondent sensor using, at least in part, the established security circuit pattern.